/*
 * Copyright (c) 2015 Eric Wilde.
 * Copyright 1998-2015 David Shapiro.
 * 
 * RSA.js is a suite of routines for performing RSA public-key computations
 * in JavaScript.  The cryptographic functions herein are used for encoding
 * and decoding strings to be sent over unsecure channels.
 *
 * To use these routines, a pair of public/private keys is created through a
 * number of means (OpenSSL tools on Linux/Unix, Dave Shapiro's
 * RSAKeyGenerator program on Windows).  These keys are passed to RSAKeyPair
 * as hexadecimal strings to create an encryption key object.  This key object
 * is then used with encryptedString to encrypt blocks of plaintext using the
 * public key.  The resulting cyphertext blocks can be decrypted with
 * decryptedString.
 *
 * Note that the cryptographic functions herein are complementary to those
 * found in CryptoFuncs.php and CryptoFuncs.pm.  Hence, encrypted messages may
 * be sent between programs written in any of those languages.  The most
 * useful, of course is to send messages encrypted by a Web page using RSA.js
 * to a PHP or Perl script running on a Web servitron.
 *
 * Also, the optional padding flag may be specified on the call to
 * encryptedString, in which case blocks of cyphertext that are compatible
 * with real crypto libraries such as OpenSSL or Microsoft will be created.
 * These blocks of cyphertext can then be sent to Web servitron that uses one
 * of these crypto libraries for decryption.  This allows messages encrypted
 * with longer keys to be decrypted quickly on the Web server as well as
 * making for more secure communications when a padding algorithm such as
 * PKCS1v1.5 is used.
 *
 * These routines require BigInt.js and Barrett.js.
 */

/*****************************************************************************/

/*
 * Modifications
 * -------------
 *
 * 2014 Jan 11  E. Wilde       Add optional padding flag to encryptedString
 *                             for compatibility with real crypto libraries
 *                             such as OpenSSL or Microsoft.  Add PKCS1v1.5
 *                             padding.
 *
 * 2015 Jan 5  D. Shapiro      Add optional encoding flag for encryptedString
 *                             and encapsulate padding and encoding constants
 *                             in RSAAPP object.
 *
 * Original Code
 * -------------
 *
 * Copyright 1998-2005 David Shapiro.
 *
 * You may use, re-use, abuse, copy, and modify this code to your liking, but
 * please keep this header.
 *
 * Thanks!
 * 
 * Dave Shapiro
 * dave@ohdave.com
 */

/** ************************************************************************** */

var RSAAPP = {};

RSAAPP.NoPadding = "NoPadding";
RSAAPP.PKCS1Padding = "PKCS1Padding";
RSAAPP.RawEncoding = "RawEncoding";
RSAAPP.NumericEncoding = "NumericEncoding"

/** ************************************************************************** */

function RSAKeyPair(encryptionExponent, decryptionExponent, modulus, keylen)
/*
 * encryptionExponent The encryption exponent (i.e. public encryption key) to be
 * used for encrypting messages. If you aren't doing any encrypting, a dummy
 * exponent such as "10001" can be passed.
 * 
 * decryptionExponent The decryption exponent (i.e. private decryption key) to
 * be used for decrypting messages. If you aren't doing any decrypting, a dummy
 * exponent such as "10001" can be passed.
 * 
 * modulus The modulus to be used both for encrypting and decrypting messages.
 * 
 * keylen The optional length of the key, in bits. If omitted, RSAKeyPair will
 * attempt to derive a key length (but, see the notes below).
 * 
 * returns The "new" object creator returns an instance of a key object that can
 * be used to encrypt/decrypt messages.
 * 
 * This routine is invoked as the first step in the encryption or decryption
 * process to take the three numbers (expressed as hexadecimal strings) that are
 * used for RSA asymmetric encryption/decryption and turn them into a key object
 * that can be used for encrypting and decrypting.
 * 
 * The key object is created thusly:
 * 
 * RSAKey = new RSAKeyPair("ABC12345", 10001, "987654FE");
 * 
 * or:
 * 
 * RSAKey = new RSAKeyPair("ABC12345", 10001, "987654FE", 64);
 * 
 * Note that RSAKeyPair will try to derive the length of the key that is being
 * used, from the key itself. The key length is especially useful when one of
 * the padding options is used and/or when the encrypted messages created by the
 * routine encryptedString are exchanged with a real crypto library such as
 * OpenSSL or Microsoft, as it determines how many padding characters are
 * appended.
 * 
 * Usually, RSAKeyPair can determine the key length from the modulus of the key
 * but this doesn't always work properly, depending on the actual value of the
 * modulus. If you are exchanging messages with a real crypto library, such as
 * OpenSSL or Microsoft, that depends on the fact that the blocks being passed
 * to it are properly padded, you'll want the key length to be set properly. If
 * that's the case, of if you just want to be sure, you should specify the key
 * length that you used to generated the key, in bits when this routine is
 * invoked.
 */
{
	/*
	 * Convert from hexadecimal and save the encryption/decryption exponents and
	 * modulus as big integers in the key object.
	 */
	this.e = biFromHex(encryptionExponent);
	this.d = biFromHex(decryptionExponent);
	this.m = biFromHex(modulus);
	/*
	 * Using big integers, we can represent two bytes per element in the big
	 * integer array, so we calculate the chunk size as:
	 * 
	 * chunkSize = 2 * (number of digits in modulus - 1)
	 * 
	 * Since biHighIndex returns the high index, not the number of digits, the
	 * number 1 has already been subtracted from its answer.
	 * 
	 * However, having said all this, "User Knows Best". If our caller passes us
	 * a key length (in bits), we'll treat it as gospel truth.
	 */
	if (typeof (keylen) != 'number') {
		this.chunkSize = 2 * biHighIndex(this.m);
	} else {
		this.chunkSize = keylen / 8;
	}

	this.radix = 16;
	/*
	 * Precalculate the stuff used for Barrett modular reductions.
	 */
	this.barrett = new BarrettMu(this.m);
}

/** ************************************************************************** */

function encryptedString(key, s, pad, encoding)
/*
 * key The previously-built RSA key whose public key component is to be used to
 * encrypt the plaintext string.
 * 
 * s The plaintext string that is to be encrypted, using the RSA assymmetric
 * encryption method.
 * 
 * pad The optional padding method to use when extending the plaintext to the
 * full chunk size required by the RSA algorithm. To maintain compatibility with
 * other crypto libraries, the padding method is described by a string. The
 * default, if not specified is "OHDave". Here are the choices:
 * 
 * OHDave - this is the original padding method employed by Dave Shapiro and Rob
 * Saunders. If this method is chosen, the plaintext can be of any length. It
 * will be padded to the correct length with zeros and then broken up into
 * chunks of the correct length before being encrypted. The resultant cyphertext
 * blocks will be separated by blanks.
 * 
 * Note that the original code by Dave Shapiro reverses the byte order to
 * little-endian, as the plaintext is encrypted. If either these JavaScript
 * routines or one of the complementary PHP/Perl routines derived from this code
 * is used for decryption, the byte order will be reversed again upon decryption
 * so as to come out correctly.
 * 
 * Also note that this padding method is claimed to be less secure than
 * PKCS1Padding.
 * 
 * NoPadding - this method truncates the plaintext to the length of the RSA key,
 * if it is longer. If its length is shorter, it is padded with zeros. In either
 * case, the plaintext string is reversed to preserve big-endian order before it
 * is encrypted to maintain compatibility with real crypto libraries such as
 * OpenSSL or Microsoft. When the cyphertext is to be decrypted by a crypto
 * library, the library routine's RSAAPP.NoPadding flag, or its equivalent,
 * should be used.
 * 
 * Note that this padding method is claimed to be less secure than PKCS1Padding.
 * 
 * PKCS1Padding - the PKCS1v1.5 padding method (as described in RFC 2313) is
 * employed to pad the plaintext string. The plaintext string must be no longer
 * than the length of the RSA key minus 11, since PKCS1v1.5 requires 3 bytes of
 * overhead and specifies a minimum pad of 8 bytes. The plaintext string is
 * padded with randomly-generated bytes and then its order is reversed to
 * preserve big-endian order before it is encrypted to maintain compatibility
 * with real crypto libraries such as OpenSSL or Microsoft. When the cyphertext
 * is to be decrypted by a crypto library, the library routine's
 * RSAAPP.PKCS1Padding flag, or its equivalent, should be used.
 * 
 * encoding The optional encoding scheme to use for the return value. If
 * ommitted, numeric encoding will be used.
 * 
 * RawEncoding - The return value is given as its raw value. This is the easiest
 * method when interoperating with server-side OpenSSL, as no additional
 * conversion is required. Use the constant RSAAPP.RawEncoding for this option.
 * 
 * NumericEncoding - The return value is given as a number in hexadecimal.
 * Perhaps useful for debugging, but will need to be translated back to its raw
 * equivalent (e.g. using PHP's hex2bin) before using with OpenSSL. Use the
 * constant RSAAPP.NumericEncoding for this option.
 * 
 * returns The cyphertext block that results from encrypting the plaintext
 * string s with the RSA key.
 * 
 * This routine accepts a plaintext string that is to be encrypted with the
 * public key component of the previously-built RSA key using the RSA
 * assymmetric encryption method. Before it is encrypted, the plaintext string
 * is padded to the same length as the encryption key for proper encryption.
 * 
 * Depending on the padding method chosen, an optional header with block type is
 * prepended, the plaintext is padded using zeros or randomly-generated bytes,
 * and then the plaintext is possibly broken up into chunks.
 * 
 * Note that, for padding with zeros, this routine was altered by Rob Saunders
 * (rob@robsaunders.net). The new routine pads the string after it has been
 * converted to an array. This fixes an incompatibility with Flash MX's
 * ActionScript.
 * 
 * The various padding schemes employed by this routine, and as presented to RSA
 * for encryption, are shown below. Note that the RSA encryption done herein
 * reverses the byte order as encryption is done:
 * 
 * Plaintext In ------------
 * 
 * d5 d4 d3 d2 d1 d0
 * 
 * OHDave ------
 * 
 * d5 d4 d3 d2 d1 d0 00 00 00 /.../ 00 00 00 00 00 00 00 00
 * 
 * NoPadding ---------
 * 
 * 00 00 00 00 00 00 00 00 00 /.../ 00 00 d0 d1 d2 d3 d4 d5
 * 
 * PKCS1Padding ------------
 * 
 * d0 d1 d2 d3 d4 d5 00 p0 p1 /.../ p2 p3 p4 p5 p6 p7 02 00 \------------
 * ------------/ \/ Minimum 8 bytes pad length
 */
{
	var a = new Array(); // The usual Alice and Bob stuff
	var sl = s.length; // Plaintext string length
	var i, j, k; // The usual Fortran index stuff
	var padtype; // Type of padding to do
	var encodingtype; // Type of output encoding
	var rpad; // Random pad
	var al; // Array length
	var result = ""; // Cypthertext result
	var block; // Big integer block to encrypt
	var crypt; // Big integer result
	var text; // Text result
	/*
	 * Figure out the padding type.
	 */

	if (typeof (pad) == 'string') {
		if (pad == RSAAPP.NoPadding) {
			padtype = 1;
		} else if (pad == RSAAPP.PKCS1Padding) {
			padtype = 2;
		} else {
			padtype = 0;
		}
	} else {
		padtype = 0;
	}
	/*
	 * Determine encoding type.
	 */
	if (typeof (encoding) == 'string' && encoding == RSAAPP.RawEncoding) {
		encodingtype = 1;
	} else {
		encodingtype = 0;
	}

	/*
	 * If we're not using Dave's padding method, we need to truncate long
	 * plaintext blocks to the correct length for the padding method used:
	 * 
	 * NoPadding - key length PKCS1Padding - key length - 11
	 */
	if (padtype == 1) {
		if (sl > key.chunkSize) {
			sl = key.chunkSize;
		}
	} else if (padtype == 2) {
		if (sl > (key.chunkSize - 11)) {
			sl = key.chunkSize - 11;
		}
	}
	/*
	 * Convert the plaintext string to an array of characters so that we can
	 * work with individual characters.
	 * 
	 * Note that, if we're talking to a real crypto library at the other end, we
	 * reverse the plaintext order to preserve big-endian order.
	 */
	i = 0;

	if (padtype == 2) {
		j = sl - 1;
	} else {
		j = key.chunkSize - 1;
	}

	while (i < sl) {
		if (padtype) {
			a[j] = s.charCodeAt(i);
		} else {
			a[i] = s.charCodeAt(i);
		}

		i++;
		j--;
	}
	/*
	 * Now is the time to add the padding.
	 * 
	 * If we're doing PKCS1v1.5 padding, we pick up padding where we left off
	 * and pad the remainder of the block. Otherwise, we pad at the front of the
	 * block. This gives us the correct padding for big-endian blocks.
	 * 
	 * The padding is either a zero byte or a randomly-generated non-zero byte.
	 */
	if (padtype == 1) {
		i = 0;
	}

	j = key.chunkSize - (sl % key.chunkSize);

	while (j > 0) {
		if (padtype == 2) {
			rpad = Math.floor(Math.random() * 256);

			while (!rpad) {
				rpad = Math.floor(Math.random() * 256);
			}

			a[i] = rpad;
		} else {
			a[i] = 0;
		}

		i++;
		j--;
	}
	/*
	 * For PKCS1v1.5 padding, we need to fill in the block header.
	 * 
	 * According to RFC 2313, a block type, a padding string, and the data shall
	 * be formatted into the encryption block:
	 * 
	 * EncrBlock = 00 || BlockType || PadString || 00 || Data
	 * 
	 * The block type shall be a single octet indicating the structure of the
	 * encryption block. For this version of the document it shall have value
	 * 00, 01, or 02. For a private-key operation, the block type shall be 00 or
	 * 01. For a public-key operation, it shall be 02.
	 * 
	 * The padding string shall consist of enough octets to pad the encryption
	 * block to the length of the encryption key. For block type 00, the octets
	 * shall have value 00; for block type 01, they shall have value FF; and for
	 * block type 02, they shall be pseudorandomly generated and nonzero.
	 * 
	 * Note that in a previous step, we wrote padding bytes into the first three
	 * bytes of the encryption block because it was simpler to do so. We now
	 * overwrite them.
	 */
	if (padtype == 2) {
		a[sl] = 0;
		a[key.chunkSize - 2] = 2;
		a[key.chunkSize - 1] = 0;
	}
	/*
	 * Carve up the plaintext and encrypt each of the resultant blocks.
	 */
	al = a.length;

	for (i = 0; i < al; i += key.chunkSize) {
		/*
		 * Get a block.
		 */
		block = new BigInt();

		j = 0;

		for (k = i; k < (i + key.chunkSize); ++j) {
			block.digits[j] = a[k++];
			block.digits[j] += a[k++] << 8;
		}
		/*
		 * Encrypt it, convert it to text, and append it to the result.
		 */
		crypt = key.barrett.powMod(block, key.e);
		if (encodingtype == 1) {
			text = biToBytes(crypt);
		} else {
			text = (key.radix == 16) ? biToHex(crypt) : biToString(crypt,
					key.radix);
		}
		result += text;
	}
	/*
	 * Return the result, removing the last space.
	 */
	// result = (result.substring(0, result.length - 1));
	return result;
}

/** ************************************************************************** */

function decryptedString(key, c)
/*
 * key The previously-built RSA key whose private key component is to be used to
 * decrypt the cyphertext string.
 * 
 * c The cyphertext string that is to be decrypted, using the RSA assymmetric
 * encryption method.
 * 
 * returns The plaintext block that results from decrypting the cyphertext
 * string c with the RSA key.
 * 
 * This routine is the complementary decryption routine that is meant to be used
 * for JavaScript decryption of cyphertext blocks that were encrypted using the
 * OHDave padding method of the encryptedString routine (in this module). It can
 * also decrypt cyphertext blocks that were encrypted by RSAEncode (in
 * CryptoFuncs.pm or CryptoFuncs.php) so that encrypted messages can be sent of
 * insecure links (e.g. HTTP) to a Web page.
 * 
 * It accepts a cyphertext string that is to be decrypted with the public key
 * component of the previously-built RSA key using the RSA assymmetric
 * encryption method. Multiple cyphertext blocks are broken apart, if they are
 * found in c, and each block is decrypted. All of the decrypted blocks are
 * concatenated back together to obtain the original plaintext string.
 * 
 * This routine assumes that the plaintext was padded to the same length as the
 * encryption key with zeros. Therefore, it removes any zero bytes that are
 * found at the end of the last decrypted block, before it is appended to the
 * decrypted plaintext string.
 * 
 * Note that the encryptedString routine (in this module) works fairly quickly
 * simply by virtue of the fact that the public key most often chosen is quite
 * short (e.g. 0x10001). This routine does not have that luxury. The decryption
 * key that it must employ is the full key length. For long keys, this can
 * result in serious timing delays (e.g. 7-8 seconds to decrypt using 2048 bit
 * keys on a reasonably fast machine, under the Firefox Web browser).
 * 
 * If you intend to send encrypted messagess to a JavaScript program running
 * under a Web browser, you might consider using shorter keys to keep the
 * decryption times low. Alternately, a better scheme is to generate a random
 * key for use by a symmetric encryption algorithm and transmit it to the other
 * end, after encrypting it with encryptedString. The other end can use a real
 * crypto library (e.g. OpenSSL or Microsoft) to decrypt the key and then use it
 * to encrypt all of the messages (with a symmetric encryption algorithm such as
 * Twofish or AES) bound for the JavaScript program. Symmetric decryption is
 * orders of magnitude faster than asymmetric and should yield low decryption
 * times, even when executed in JavaScript.
 * 
 * Also note that only the OHDave padding method (e.g. zeros) is supported by
 * this routine *AND* that this routine expects little-endian cyphertext, as
 * created by the encryptedString routine (in this module) or the RSAEncode
 * routine (in either CryptoFuncs.pm or CryptoFuncs.php). You can use one of the
 * real crypto libraries to create cyphertext that can be decrypted by this
 * routine, if you reverse the plaintext byte order first and then manually pad
 * it with zero bytes. The plaintext should then be encrypted with the NoPadding
 * flag or its equivalent in the crypto library of your choice.
 */
{
	var blocks = c.split(" "); // Multiple blocks of cyphertext
	var b; // The usual Alice and Bob stuff
	var i, j; // The usual Fortran index stuff
	var bi; // Cyphertext as a big integer
	var result = ""; // Plaintext result
	/*
	 * Carve up the cyphertext into blocks.
	 */

	for (i = 0; i < blocks.length; ++i) {
		/*
		 * Depending on the radix being used for the key, convert this
		 * cyphertext block into a big integer.
		 */
		if (key.radix == 16) {
			bi = biFromHex(blocks[i]);
		} else {
			bi = biFromString(blocks[i], key.radix);
		}
		/*
		 * Decrypt the cyphertext.
		 */
		b = key.barrett.powMod(bi, key.d);
		/*
		 * Convert the decrypted big integer back to the plaintext string. Since
		 * we are using big integers, each element thereof represents two bytes
		 * of plaintext.
		 */
		for (j = 0; j <= biHighIndex(b); ++j) {
			result += String.fromCharCode(b.digits[j] & 255, b.digits[j] >> 8);
		}
	}
	/*
	 * Remove trailing null, if any.
	 */
	if (result.charCodeAt(result.length - 1) == 0) {
		result = result.substring(0, result.length - 1);
	}
	/*
	 * Return the plaintext.
	 */
	return (result);
}
